﻿namespace AdvancedTraining.Lesson35;

/// <summary>
/// 最长递增子序列的个数 - LeetCode 673
/// 给定一个未排序的整数数组，找到最长递增子序列的个数。
///
/// 算法思路：
/// 1. FindNumberOfLis1：O(N^2)动态规划解法
///    - lens[i]表示以nums[i]结尾的最长递增子序列长度
///    - cnts[i]表示以nums[i]结尾的最长递增子序列个数
///    - 对于每个i，遍历之前的所有j来更新lens和cnts
/// 2. FindNumberOfLis2：O(N*logN)优化解法
///    - 使用SortedDictionary模拟Java的TreeMap
///    - dp[i]存储长度为i+1的递增子序列的信息
///    - 通过二分查找确定当前元素应该插入的位置
/// </summary>
public class NumberOfLongestIncreasingSubsequence
{
    /// <summary>
    /// 好理解的方法，时间复杂度O(N^2)
    /// 动态规划解法：对于每个元素，统计其作为结尾的最长递增子序列长度和个数
    /// </summary>
    /// <param name="numbers">输入数组</param>
    /// <returns>最长递增子序列的个数</returns>
    public static int FindNumberOfLis1(int[]? numbers)
    {
        if (numbers == null || numbers.Length == 0) return 0;

        var n = numbers.Length;
        var lens = new int[n];
        var cnts = new int[n];
        lens[0] = 1;
        cnts[0] = 1;
        var maxLen = 1;
        var allCnt = 1;
        for (var i = 1; i < n; i++)
        {
            var preLen = 0;
            var preCnt = 1;
            for (var j = 0; j < i; j++)
            {
                if (numbers[j] >= numbers[i] || preLen > lens[j]) continue;

                if (preLen < lens[j])
                {
                    preLen = lens[j];
                    preCnt = cnts[j];
                }
                else
                {
                    preCnt += cnts[j];
                }
            }

            lens[i] = preLen + 1;
            cnts[i] = preCnt;
            if (maxLen < lens[i])
            {
                maxLen = lens[i];
                allCnt = cnts[i];
            }
            else if (maxLen == lens[i])
            {
                allCnt += cnts[i];
            }
        }

        return allCnt;
    }

    /// <summary>
    /// 优化后的最优解，时间复杂度O(N*logN)
    /// 使用SortedDictionary模拟Java的TreeMap来实现优化算法
    /// </summary>
    /// <param name="numbers">输入数组</param>
    /// <returns>最长递增子序列的个数</returns>
    public static int FindNumberOfLis2(int[]? numbers)
    {
        if (numbers == null || numbers.Length == 0) return 0;

        var dp = new List<SortedDictionary<int, int>>();
        foreach (var num in numbers)
        {
            // num之前的长度，num到哪个长度len+1
            var len = Search(dp, num);
            // cnt : 最终要去加底下的记录，才是应该填入的value
            int cnt;
            if (len == 0)
            {
                cnt = 1;
            }
            else
            {
                var p = dp[len - 1];
                // 模拟Java的TreeMap.ceilingKey()方法：找到>=num的最小键，如果不存在则为null
                var ceilingEntry = p.FirstOrDefault(x => x.Key >= num);
                cnt = p.First().Value - (ceilingEntry.Equals(default(KeyValuePair<int, int>)) ? 0 : p[ceilingEntry.Key]);
            }

            if (len == dp.Count)
            {
                dp.Add(new SortedDictionary<int, int>());
                dp[len][num] = cnt;
            }
            else
            {
                dp[len][num] = dp[len].First().Value + cnt;
            }
        }

        return dp[^1].First().Value;
    }

    /// <summary>
    /// 二分查找，返回>=num最左的位置
    /// 在dp列表中找到第一个元素的最小键值大于等于num的位置
    /// </summary>
    /// <param name="dp">SortedDictionary列表</param>
    /// <param name="num">目标数字</param>
    /// <returns>=num的最左位置索引</returns>
    private static int Search(List<SortedDictionary<int, int>> dp, int num)
    {
        int l = 0, r = dp.Count - 1;
        var ans = dp.Count;
        while (l <= r)
        {
            var m = (l + r) / 2;
            if (dp[m].First().Key >= num)
            {
                ans = m;
                r = m - 1;
            }
            else
            {
                l = m + 1;
            }
        }

        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 最长递增子序列个数问题测试 ===");

        // 测试用例1：基本功能测试 - LeetCode示例
        TestBasicFunctionality();

        // 测试用例2：空数组
        TestEmptyArray();

        // 测试用例3：单元素数组
        TestSingleElement();

        // 测试用例4：完全递增序列
        TestIncreasingSequence();

        // 测试用例5：完全递减序列
        TestDecreasingSequence();

        // 测试用例6：有重复元素的序列
        TestDuplicateElements();

        // 测试用例7：复杂情况
        TestComplexCase();

        // 测试用例8：对比两种算法
        TestBothAlgorithms();
    }

    private static void TestBasicFunctionality()
    {
        int[] nums = [1, 3, 5, 4, 7];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试1 - 基本功能: [1,3,5,4,7] -> O(N²):{result1}, O(N*logN):{result2} (期望: 2)");
    }

    private static void TestEmptyArray()
    {
        int[] nums = [];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试2 - 空数组: [] -> O(N²):{result1}, O(N*logN):{result2} (期望: 0)");
    }

    private static void TestSingleElement()
    {
        int[] nums = [10];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试3 - 单元素: [10] -> O(N²):{result1}, O(N*logN):{result2} (期望: 1)");
    }

    private static void TestIncreasingSequence()
    {
        int[] nums = [1, 2, 3, 4, 5];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试4 - 完全递增: [1,2,3,4,5] -> O(N²):{result1}, O(N*logN):{result2} (期望: 1)");
    }

    private static void TestDecreasingSequence()
    {
        int[] nums = [5, 4, 3, 2, 1];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试5 - 完全递减: [5,4,3,2,1] -> O(N²):{result1}, O(N*logN):{result2} (期望: 5)");
    }

    private static void TestDuplicateElements()
    {
        int[] nums = [2, 2, 2, 2, 2];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试6 - 重复元素: [2,2,2,2,2] -> O(N²):{result1}, O(N*logN):{result2} (期望: 5)");
    }

    private static void TestComplexCase()
    {
        int[] nums = [1, 2, 4, 3, 5, 4, 7, 2];
        int result1 = FindNumberOfLis1(nums);
        int result2 = FindNumberOfLis2(nums);
        Console.WriteLine($"测试7 - 复杂情况: [1,2,4,3,5,4,7,2] -> O(N²):{result1}, O(N*logN):{result2} (期望: 3)");
    }

    private static void TestBothAlgorithms()
    {
        Console.WriteLine("\n=== 算法性能对比测试 ===");
        var testCases = new[]
        {
            new[] { 1, 3, 5, 4, 7 },
            new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
            new[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 },
            new[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
        };

        for (int i = 0; i < testCases.Length; i++)
        {
            var testArray = testCases[i];
            Console.WriteLine($"测试用例{i + 1}: [{string.Join(",", testArray)}]");
            Console.WriteLine($"  O(N²)算法结果: {FindNumberOfLis1(testArray)}");
            Console.WriteLine($"  O(N*logN)算法结果: {FindNumberOfLis2(testArray)}");
        }
    }
}